package com.hanlp.top_interview_150.数组;

/**
 * 169. 多数元素
 * 摩尔投票法
 * 从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个
 */
public class A05 {
    public static void main(String[] args) {

    }

    public static int majorityElement(int[] nums) {
        int count = 1;
        int ret = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(ret == nums[i]){
                count++;
            }else {
                count--;
                if(count == 0){
                    count = 1;
                    ret = nums[++i];
                }
            }
        }
        return ret;
    }


}
